import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }

        Deque<Integer> path = new ArrayDeque<>();

        dfs(nums, n, 0, path, res);
        return res;
    }

    private void dfs(int[] nums, int n, int depth, Deque<Integer> path, List<List<Integer>> res) {
        if (depth == n) {
            res.add(new ArrayList<>(path));
            return;
        }

        path.addLast(nums[depth]);
        dfs(nums, n, depth+1, path, res);
        path.removeLast();
        dfs(nums, n, depth+1, path, res);
    }

    /**
     * 二进制枚举
     *      作者：力扣官方题解
    链接：https://leetcode.cn/problems/subsets/solutions/420294/zi-ji-by-leetcode-solution/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> t = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
}